package com.hy;

import java.util.Stack;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:132 模式
 *
 * 给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，
 * 并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。
 * 如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。
 *
 * author: Mr.Du
 * Date: 2023/12/19
 * Time: 16:08
 */
public class Find132pattern {

    public boolean find132pattern(int[] nums) {
        int last = Integer.MIN_VALUE;
        Stack<Integer> stack = new Stack<>();
        for(int i = 0;i < nums.length;i++){
            if(nums[i] < last) return true;
            while(!stack.isEmpty() && nums[i] < stack.peek()){
                last = stack.pop();
            }
            stack.push(nums[i]);

        }
        return false;
    }


    public static void main(String[] args) {
        Find132pattern find132pattern = new Find132pattern();
        int[] nums = {1,0,1,-4,-3};
        find132pattern.find132pattern(nums);
    }
}
